package com.peng.binary;

/**
 * 二分相关练习：
 * 1、普通二分搜索
 * 2、二分搜索第一次出现的位置
 * 3、二分搜索>=最左侧位置
 * 4、二分搜索<=最右侧位置
 * 5、局部最小问题
 */
public class BinarySearchTest {


    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 5, 6, 7};

        int i = binarySearch(arr, 5);
        int j = binarySearchFirst(arr, 5);
        int k = binarySearchEqAndMoreLeft(arr, 4);
        int w = binarySearchEqAndLessRight(arr, 4);
        System.out.println(i);
        System.out.println(j);
        System.out.println(k);
        System.out.println(w);


    }

    /**
     * normal binary search example~
     *
     * @param arr
     * @param findNum
     * @return
     */
    private static int binarySearch(int[] arr, int findNum) {
        int L = 0;
        int R = arr.length - 1;

        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] > findNum) {
                R = mid - 1;

            } else if (arr[mid] < findNum) {
                L = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 查找最早出现这个数的位置
     *
     * @param arr
     * @param findNum
     * @return
     */
    private static int binarySearchFirst(int[] arr, int findNum) {
        int L = 0;
        int R = arr.length - 1;

        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] > findNum) {
                R = mid - 1;

            } else if (arr[mid] < findNum) {
                L = mid + 1;
            } else {
                index = mid;
                break;
            }
        }
        while (arr[index - 1] == arr[index]) {
            index--;
        }


        return index;
    }


    /**
     * 查找>=这个数，最左边的位置
     *
     * @param arr
     * @param findNum
     * @return
     */
    private static int binarySearchEqAndMoreLeft(int[] arr, int findNum) {
        int L = 0;
        int R = arr.length - 1;

        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= findNum) {
                R = mid - 1;
                index = mid;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }


    /**
     * 查找<=这个数，最右边的位置
     *
     * @param arr
     * @param findNum
     * @return
     */
    private static int binarySearchEqAndLessRight(int[] arr, int findNum) {
        int L = 0;
        int R = arr.length - 1;

        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= findNum) {
                R = mid - 1;
            } else {
                index = mid;
                L = mid + 1;
            }
        }
        return index;
    }


    /**
     * 不要求数据有序性，却可以进行二分的例子：
     * 局部最小问题：
     * 1、最左侧局部最小： 0位置的值<1位置的值
     * 2、最右侧局部最小： N位置的值<N-1位置的值
     * 3、普通局部最小： 在i位置上： arr[i-1]>arr[i]  && arr[i+1]>arr[i]
     *
     * @param arr
     * @return
     */
    private static int regionMin(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        //最左侧局部最小检测
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        //最右侧局部最小检测
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }

        //常规局部最小检测
        int L = 1;
        int R = arr.length - 2;
        while (L < R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] > arr[mid + 1]) {
                L = mid + 1;
            } else if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else {
                return mid;
            }
        }
        //这种情况是出现在如果只有三个数的情况下，
        //数据集不符合最左局部最小值，也不符合最右局部最小值
        //那么局部最小值必定在中间值【1】位置上
        return L;


    }


}
